/*
回溯法，集合递归法和穷举，把每个可能回溯一遍
 */
package com.test.zero1package;

public class BackTracking {
    static int[] w = {2, 3, 4, 5};
    static int[] v = {3, 4, 5, 6};
    static int number = 4, capacity = 9;

    public static void main(String[] args) {
        System.out.println(value(0,0));  //回溯法，是从第1个物品开始的，重量是从0开始的
    }

    static int value(int index, int weight){  //使用两个变量，index跟踪第几个物品，weight表示当前重量
        if (index >= w.length) return 0;  //索引大于数组的长度，超出了，跳出递归
        if (weight + w[index] > capacity) return 0;  //背包当前重量+当前索引的物品重量>承重量时，也跳出

        /*
        下面这个语句，是用来比较当前背包的价值+下一个物品放进来后的价值，与不放下一个物品比较（索引+1，物品不放，重量不加）
        每轮到1个物品，只有选和不选两种情况，选的话就把当前物品的价值加上，并递归调用函数自己，把当前物品的重量考虑进去；
        不选的话，继续下一个物品，当前物品没选，所用递归调用传进去的重量为0
         */
        return Math.max(value(index + 1, weight + w[index])+ v[index], value(index + 1,weight));
    }
}
